package com.cwj.lab1;

import java.util.Stack;

/**
 * 链栈，即用单链表实现的后入先出的栈
 */
public class LinkStack<T> {
    //链式栈的结点定义
    //即单链表
    class Node {
        T val;//数据域
        Node next;//指针域

        public Node(T val, Node next) {
            this.val = val;
            this.next = next;
        }
    }

    //链表的头结点
    Node top;
    //栈的元素数目
    int len;

    //栈的构造器：其有设置一个头结点（数据域无用）
    public LinkStack() {
        len = 0;
        top = new Node(null, null);
    }

    /**
     * 压栈
     * 注意：其利用头插法来压栈
     */
    public void push(T one) {
        Node nn = new Node(one, top.next);
        top.next = nn;
        len += 1;
    }

    /**
     * 弹出栈顶
     */
    public T pop() {
        check();//即必须在非空白的情况下来进行弹出
        T temp = top.next.val;
        top.next = top.next.next;
        len -= 1;
        return temp;
    }

    /**
     * 取出栈顶元素，但没有弹出
     */
    public T peek() {
        check();
        return top.next.val;
    }

    /**
     * 若栈为空集返回true;否则为false
     */
    public boolean isEmpty() {
        return this.len <= 0;
    }

    //其是检测单当栈为空时，是否有对齐进行删除或取值新闻
    private void check() {
        if (top.next == null) {
            throw new RuntimeException("stack为空");
        }
    }

    public int size() {
        return this.len;
    }

    /**
     * 清空栈，但是其是因为在java不用释放结点空间
     */
    public void clear() {
        len = 0;
        top.next = null;
    }

    //用于调试的函数，实现
    public void showln() {
        this.show();
        System.out.println();
    }

    public void show() {
        Node flag = this.top.next;
        System.out.print("{");
        while (flag != null) {
            System.out.print(flag.val + " ");
            flag = flag.next;
        }
        System.out.print("}");
    }

    //测试代码
    public static void main(String[] args) {
        Stack<Integer> sta = new Stack<>();
        LinkStack<Integer> mySta = new LinkStack<>();
        for (int i = 0; i < 60; i += 1) {
            choose(sta, mySta, (int) (Math.random() * 2) + 1);
            if ((i + 1) % 5 == 0) {
                System.out.print("\t");
                choose(sta, mySta, 3);
            }
            System.out.print("\t myStack=");
            mySta.showln();
        }
    }

    public static void choose(Stack<Integer> sta, LinkStack<Integer> mySta, int num) {
        int data = (int) (Math.random() * 500);
        switch (num) {
            case 1:
                System.out.print("将" + data + "压栈：");
                sta.add(data);
                mySta.push(data);
                break;
            case 2:
                if (mySta.isEmpty()) {
                    System.out.print("栈空");
                    break;
                }
                System.out.print("弹栈1次");
                sta.pop();
                mySta.pop();
                break;
            case 3:
                if (mySta.isEmpty()) {
                    System.out.print("栈空");
                    break;
                }
                System.out.print("Stack=" + sta.peek());
                System.out.print("my=" + mySta.peek());
//                System.out.println();
                break;
        }
    }
}
